/*
 * =====================================================================================
 *
 *       Filename:  bstree.cpp
 *
 *    Description:  二叉搜索树
 *
 *        Version:  1.0
 *        Created:  2011-11-5 22:06:19
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *        Company:
 *
 * =====================================================================================
 */

#include "bstree.h"
#include <vector>
#include <algorithm>
#include <ctime>
#include <iostream>

#define LARGE_COUNT 20

int main(int argc, char *argv[])
{
    typedef bs_tree<long, long, identity<long> > Tree;
    Tree t;
    std::vector<int> A;

    for (int i = 0; i < LARGE_COUNT; ++i) {
        A.push_back(i);
    }

    srand((unsigned int) getpid());
    random_shuffle(A.begin(), A.end());

    for (std::vector<int>::const_iterator cit = A.begin(); cit != A.end(); ++cit) {
        t.insert(*cit);
    }

    t.inorder();
    std::cout << "\n--------------------\n";
    std::cout << "the binary search tree's depth is " << t.depth() << std::endl;
    t.level_order();
    std::cout << "\n--------------------\n";
    std::cout << "iterator the binary tree : ";

    for (Tree::iterator it = t.begin(); it != t.end(); ++it) {
        std::cout << *it << " ";
    }

    std::cout << std::endl;
    t.level_order();

    for (int i = 1; i <= LARGE_COUNT; ++i) {
        std::cout << "select the " << i << "th number is " << *(t.select(i)) << std::endl;
    }

    std::cout << "select the -1th number is " << (t.select(-1) == t.end() ? "false" : "true") << std::endl;
    std::cout << "select the 0th number is " << (t.select(0) == t.end() ? "false" : "true") << std::endl;
    std::cout << "select the 30th number is " << (t.select(30) == t.end() ? "false" : "true") << std::endl;
    Tree::iterator find8it = t.find(8);
    std::cout << "find the number 8 is " << ((find8it != t.end()) ? "true" : "false") << std::endl;
    t.erase(8);
    find8it = t.find(8);
    std::cout << "erase the number 8 and find again is " << ((find8it == t.end()) ? "true" : "false") << std::endl;
    std::cout << "find the number 10's successor is " << *(++t.find(10)) << std::endl;
    std::cout << "find the number 10's predecessor is " << *(--t.find(10)) << std::endl;
    std::cout << "find the number 20's successor is " << *(++t.find(19)) << std::endl;
    std::cout << "find the number 0's predecessor is " << *(--t.find(0)) << std::endl;
    std::cout << "\n--------------------\n";

    std::vector<int> A2;

    for (int i = -LARGE_COUNT; i < LARGE_COUNT + 1; ++i) {
        A2.push_back(i);
    }

    srand((unsigned int) getpid());
    random_shuffle(A2.begin(), A2.end());

    Tree t2;

    for (std::vector<int>::const_iterator cit = A2.begin(); cit != A2.end(); ++cit) {
        t2.insertHead(*cit);
    }

    std::cout << "iterator the binary tree2 : ";

    for (Tree::iterator it = t2.begin(); it != t2.end(); ++it) {
        std::cout << *it << " ";
    }

    std::cout << std::endl;

    for (int i = 1; i <= 2 * LARGE_COUNT + 1; ++i) {
        std::cout << "select the " << i << "th number is " << *(t2.select(i)) << std::endl;
    }

    t2.level_order();

    return 0;
}
